МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
ТЕРНОПІЛЬСЬКИЙ НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ
імені Івана Пулюя
Кафедра комп’ютерних наук
ЛАБОРАТОРНА РОБОТА №6
з предмету
Теорія алгоритмів та математичні основи представлення знань
Тема: Оцінка складності алгоритмів
Тернопіль-2010
Мета роботи: Вивчення теоретичних та практичних методів оцінки cкладності алгоритмів.
Завдання до роботи
Порівняльна таблиця виконання програми лабораторних робіт №3, №4, №5
Кількість відліків = 10
№
Лабораторної
Кількість відліків
Кількість додавань
Кількість множень
Час виконання
3
20
60
120
3 мс
50
150
300
7 мс
100
300
600
26 мс
4
20
40
80
4 мс
50
100
200
5 мс
100
200
400
21 мс
5
20
210
231
6 мс
50
510
561
11 мс
100
1010
1111
33 мс
Код програми Лабораторна №3
unit Unit1;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, StdCtrls, ComCtrls, ExtCtrls, TeeProcs, TeEngine, Chart, Series;
type
TForm1 = class(TForm)
Button1: TButton;
Chart1: TChart;
Series1: TFastLineSeries;
Button2: TButton;
Label1: TLabel; Label2: TLabel; Label3: TLabel;
Label4: TLabel; Label5: TLabel; Label6: TLabel;
Label7: TLabel;
procedure Button1Click(Sender: TObject);
function Mnogenia(m1:real; m2:extended): extended;
function Dodavania(d1:extended; d2:extended): extended;
procedure Button2Click(Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
end;
const
n=20;
var
Form1: TForm1;
k_dod, k_mnog:integer;
i:integer;
x1,x2,x3,x4,x5:extended;
inx: array[1..n] of real;
outx: array[1..n] of extended;
implementation
{$R *.dfm}
procedure TForm1.Button1Click(Sender: TObject);
begin
x1:=0; x2:=0; x3:=0; x4:=0; x5:=0;
k_dod:=0; k_mnog:=0;
inx[1]:=1;
for i:=2 to n do
inx[i]:=0;
for i := 1 to n do
begin
outx[i]:=x5;
x5:= x4;
x4:=Dodavania(Mnogenia(12.3,x2),Dodavania(Mnogenia(4,x3),-x5));
x3:=x2;
x2:= Dodavania(Mnogenia(-2,x3),Dodavania(Mnogenia(11,x5),x1));
x1:=inx[i];
end;
Form1.Label1.Caption:='x1='+ floattostr(x1);
Form1.Label2.Caption:='x2='+ floattostr(x2);
Form1.Label3.Caption:='x3='+ floattostr(x3);
Form1.Label4.Caption:='x4='+ floattostr(x4);
Form1.Label5.Caption:='x5='+ floattostr(x5);
Form1.Label6.Caption:='Функція додавання викликалася '+ inttostr(k_dod);
Form1.Label7.Caption:='Функція множення викликалася '+ inttostr(k_mnog);
series1.Clear;
for i:=1 to n do
begin
Series1.Add(outx[I]) ;
end;
end;
procedure TForm1.Button2Click(Sender: TObject);
begin
close;
end;
function TForm1.Dodavania(d1:extended; d2:extended): extended;
begin
k_dod:= k_dod+1;
Dodavania:=d1+d2;
end;
function TForm1.Mnogenia(m1:real; m2:extended):extended;
begin
k_mnog:= k_mnog+1;
Mnogenia:=m1*m2;
end;end.
Код програми Лабораторна №4
unit Unit1;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, StdCtrls, ComCtrls, ExtCtrls, TeeProcs, TeEngine, Chart, Series;
type
TForm1 = class(TForm) Button1: TButton; Chart1: TChart; Series1: TFastLineSeries;
Button2: TButton; Label6: TLabel; Label7: TLabel;
procedure Button1Click(Sender: TObject);
function Mnogenia(m1:real; m2:extended): extended;
function Dodavania(d1:extended; d2:extended): extended;
procedure Button2Click(Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
end;
const
n=20;
var
Form1: TForm1;
k_dod, k_mnog:integer;
i:integer;
x1,x2,x3,x4,x5:extended;
inx: array[1..n] of real;
outx: array[1..n] of extended;
implementation
{$R *.dfm}
procedure TForm1.Button1Click(Sender: TObject);
begin
inx[1]:=1;
for i:=2 to n do
begin
inx[i]:=0;
end;
for i:=1 to n do
begin
outx[i]:= Dodavania(Dodavania(Mnogenia(12.3,inx[i]),+Mnogenia(4,inx[i-1])),Mnogenia(132,outx[i-1]))-Mnogenia(46,outx[i-...
